A lock is a synchronization mechanism used to enforce limits on access to a given resource, such as a file, memory location, I/O port, and the like, usually to ensure that only one thread of execution uses the resource at a time. Read/write locks (RW locks) are locks that allow for multiple readers to hold the lock at the same time, while only one writer at a time may hold the lock. A writer looking to obtain a RW lock must block until all readers or another writer have released the lock and, conversely, all readers seeking a RW lock must wait for a writer to release the lock to acquire it.
One problem with RW locks is the phenomenon known as unbounded priority inversion. One example of unbounded priority inversion is where there are three processes with three different priorities. These processes are known as A, B and C, where A is of highest priority and C is lowest. C takes a lock ‘L’ and is preempted by A due to priority. A then tries to take lock L but cannot because C has it. As a result, A blocks on the lock and lets C run again. But, at this point, B comes in and preempts C from running due to priority. If B is not also trying to own the lock C holds, B can keep C, and thereby A, from running for as long as it wants. The unbounded priority inversion results from B keeping A from running even though A is of higher priority than B.
Priority Inheritance (PI) is a way to prevent unbounded priority inversion. Priority inheritance provides a solution so that when a process with high priority blocks on a lock held by a process with lower priority, the owner of the lock “inherits” the priority of the process that is blocking. When the lock is released the owner loses that priority. In the above example, when A blocked on process C, C would inherit the priority of process A. Then, when B came along, B would be preempted by C's new inherited higher priority. In this way, B can no longer unwittingly preempt A. When C releases the lock, it would lose the priority of A and go back to its original priority. A would then run again, and B would have to wait for A to finish.
However, PI is a very complex solution to implement. It is complex when only dealing with locks that have a single owner. Yet, RW locks may have several owners. For example, imagine processes A, B, C, D, E, and F, where A is the highest priority, and F is the lowest. A tries to take a RW lock for write, but C, D, E and F all have it for read. If B preempts just one of C, D, E, or F and it is not seeking the lock, then B can keep the RW lock from being released for A. On a multiprocessor system, this can happen quite often. When a lock has multiple owners (such as with RW locks) the PI algorithm becomes much more complex. There have been various solutions utilized to try to overcome this difficulty.
One solution is not to implement PI on RW locks at all. This is a simple solution, but allows for the above priority inversion problem to take place. Another solution is to serialize the readers in a RW lock. This means that the lock will only allow for one reader at a time, which converts the RW lock into a simple mutual exclusion algorithm (mutex). If two readers try to take the lock, the second reader will block and have to wait for the first reader to release the lock. The problem with this solution is a loss of performance that RW locks with multiple readers provide for parallel computing.
A third solution implements large-scale locking via dynamically-allocated arrays. This solution tries to link PI and multiple reader RW locks together by allocating memory when creating new locks. When more readers need to grab the lock, more memory is allocated to store the data. However, this solution cannot be utilized inside the kernel; it can only be implemented in user space. This is because the memory management of the kernel itself uses RW locks, so no memory allocation is allowed. This solution is also slow and may be no better than the solution of serializing the readers in a RW lock.
A final solution is to limit the number of readers per RW lock. With this solution, each RW lock is given an array associated with readers that can take the lock; this array tracks the max reader limit. When more readers than the limit try to take the lock for read, they block. The problem with this solution is that it is possible to exceed the number of readers allowed. Another problem is that the kernel has thousands of locks and by making an array for each lock, it takes up a lot of memory (as the kernel has thousands of locks, and increasing each lock by X readers is huge).
A system that provides a priority inheritance solution for RW locks without requiring any special memory allocations and without limiting the number of readers that can grab the lock would be beneficial.